package xyz.scootaloo.oj.leetcode;

import xyz.scootaloo.console.app.support.Tester;

import java.util.ArrayDeque;
import java.util.Deque;

/**
 * 单调栈
 * 哨兵
 * @author flutterdash@qq.com
 * @since 2021/3/22 22:25
 */
public class P84c {

    public int largestRectangleArea(int[] heights) {
        int len = heights.length;
        if (len == 0)
            return 0;
        if (len == 1)
            return heights[0];

        int[] HEIGHTS = new int[len + 2];
        HEIGHTS[0] = 0;
        System.arraycopy(heights, 0, HEIGHTS, 1, len);
        HEIGHTS[len + 1] = 0;
        len = HEIGHTS.length;
        heights = HEIGHTS;

        /* 单调栈 */
        Deque<Integer> stack = new ArrayDeque<>(len);
        stack.addLast(0);
        int res = 0;
        for (int pos = 1; pos<len; pos++) {
            int currentHeight = heights[pos];
            // 遍历条件，从当前位置往前找，计算每个比当前位置高的矩形
            while (currentHeight < heights[stack.peekLast()]) {
                int curHeight = heights[stack.pollLast()];
                int curWidth = pos - stack.peekLast() - 1;
                res = Math.max(res, curHeight * curWidth);
            }
            stack.addLast(pos);
        }

        return res;
    }

    public static void main(String[] args) {
        Tester.createTest(new P84c()::largestRectangleArea)
                .addCase(new int[] {2, 1, 5, 5, 6, 2, 3}, 15)
                .addCase(new int[] {2, 1, 5, 6, 2, 3}, 10)
                .addCase(new int[] {0, 1, 9, 8, 7, 6, 5, 4, 3, 2, 1}, 25)
                .addCase(new int[] {0, 1, 2, 3, 4, 5, 6, 7, 8}, 20)
                .test();
    }

}
